#ifndef TREE_UTILS_H
#define TREE_UTILS_H

#include <iterator>
namespace TreeUtils
{

template<class Iterator, class T>
Iterator binary_search(Iterator begin, Iterator end, const T& key){
    Iterator Middle;
    Iterator NotFound = end;

    while(begin < end)
    {
        Middle = begin + (std::distance(begin, end) / 2);

        if(*Middle == key)
        {
            return Middle;
        }
        else if(*Middle > key)
        {
            end = Middle;
        }
        else
        {
            begin = Middle + 1;
        }
    }

    return NotFound;
}

template <class ForwardIterator, class T>
ForwardIterator lower_bound( ForwardIterator first, ForwardIterator last, const T& value ){
    ForwardIterator it;
    unsigned int count, step;
    count = std::distance(first,last);
    while (count>0)
    {
        it = first;
        step=count/2;
        std::advance (it,step);

        if (*it>value)                   // or: if (comp(*it,value)), for the comp version
            count=step;
        else {
            first = ++it;
            count-=step+1;
        }
    }
    return first;
}

}
#endif  /* TREE_UTILS_H */
